package com.zhang;

/**
 * @author ZhangJiXin
 * @Description UnionFind -- QF(快速查询)优化
 * @date 2021/4/30 9:52
 */
public  class UnionFind_QF extends UnionFind{

    public UnionFind_QF(int capacity) {
       super(capacity);
    }

    @Override
    public int find(int v){
        rangeCheck(v);
        return parents[v];
    }

    /**
     * 快速查询实现方法 合并的时间复杂度是O(n)
     * 是通过将左边集合中所有元素的根节点指向 右边集合的根节点
     * @Author ZhangJiXin
     * @Date 2021/4/30 11:19
     * @param v1:
     * @param v2:
     * @return: void
     */
    @Override
    public void union(int v1, int v2){
        int v1Root = find(v1);
        int v2Root = find(v2);
        if (v1Root == v2Root){
            return;
        }
        for (int i = 0; i < parents.length; i++) {
            if (parents[i] == v1Root){
                parents[i] = v2Root;
            }
        }
    }

}
